翻訳と辞書 Words near each other ・ Peripetoceras ・ Periphanes ・ Periphanes delphinii ・ Peripharyngeal space ・ Periphas ・ Periphas (Attic king) ・ Peripheral ・ Peripheral artery disease ・ Peripheral blood cell ・ Peripheral blood lymphocyte ・ Peripheral blood mononuclear cell ・ Peripheral bus ・ Peripheral Canal ・ Peripheral chemoreceptors ・ Peripheral consonant ・ Peripheral cycle ・ Peripheral DMA controller ・ Peripheral drift illusion ・ Peripheral edema ・ Peripheral ERA ・ Peripheral giant-cell granuloma ・ Peripheral Head-Mounted Display (PHMD) ・ Peripheral Interchange Program ・ Peripheral Interface Adapter ・ Peripheral light focusing ・ Peripheral membrane protein ・ Peripheral myelin protein 22 ・ Peripheral nationalism ・ Peripheral nerve field ・ Peripheral nerve injury Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Peripheral cycle ： ウィキペディア英語版 Peripheral cycle In graph theory, a peripheral cycle (or peripheral circuit) in an undirected graph is, intuitively, a cycle that does not separate any part of the graph from any other part. Peripheral cycles (or, as they were initially called, peripheral polygons) were first studied by , and play important roles in the characterization of planar graphs and in generating the cycle spaces of nonplanar graphs.〔.〕 ==Definitions== A peripheral cycle $C$ in a graph $G$ can be defined formally in one of several equivalent ways: *$C$ is peripheral if it is a simple cycle in a connected graph with the property that, for every two edges $e\_1$ and $e\_2$ in $G\backslash setminus\; C$, there exists a path in $G$ that starts with $e\_1$, ends with $e\_2$, and has no interior vertices belonging to $C$.〔.〕 *$C$ is peripheral if it is an induced cycle with the property that the subgraph $G\backslash setminus\; C$ formed by deleting the edges and vertices of $C$ is connected.〔This is, essentially, the definition used by . However, Bruhn distinguishes the case that $G$ has isolated vertices from disconnections caused by the removal of $C$.〕 *If $C$ is any subgraph of $G$, a ''bridge''〔Not to be confused with bridge (graph theory), a different concept.〕 of $C$ is a minimal subgraph $B$ of $G$ that is edge-disjoint from $C$ and that has the property that all of its points of attachments (vertices adjacent to edges in both $B$ and $G\backslash setminus\; B$) belong to $C$.〔.〕 A simple cycle $C$ is peripheral if it has exactly one bridge.〔This is the definition of peripheral cycles originally used by . use the same definition of a peripheral cycle, but with a different definition of a bridge that more closely resembles the induced-cycle definition for peripheral cycles.〕 The equivalence of these definitions is not hard to see: a connected subgraph of $G\backslash setminus\; C$ (together with the edges linking it to $C$), or a chord of a cycle that causes it to fail to be induced, must in either case be a bridge, and must also be an equivalence class of the binary relation on edges in which two edges are related if they are the ends of a path with no interior vertices in $C$.〔See e.g. Theorem 2.4 of , showing that the vertex sets of bridges are path-connected, see for a definition of bridges using chords and connected components, and also see for a definition of bridges using equivalence classes of the binary relation on edges.〕 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Peripheral cycle」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.